#include "mySearch.h"
#include <iostream>
#include <string>
#include <cstddef>


using namespace std;

SSTable::SSTable() : length(0), origin(NULL) {}

SSTable::SSTable(int n, int* arr) : length(n) 
{
    origin = new int[length];
    for (int i = 0; i < length; i++) 
    {
        origin[i] = arr[i];
    }
}

SSTable::~SSTable() {
        if (origin != NULL) {
            delete[] origin;
            origin = NULL;
        }
    }

int SSTable::getLength() 
{
    return length;
}

int* SSTable::getOrigin() 
{
    return origin;
}

void SSTable::setLength(int len) 
{
        length = len;
}

void SSTable::setOrigin(int* arr) {
        if (origin != NULL) {
            delete[] origin;
            origin = NULL;
        }
        origin = new int[length];
        for (int i = 0; i < length; i++) {
            origin[i] = arr[i];
        }
    }

int SSTable::binSearch(int x) {
        int left = 0, right = length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (origin[mid] == x) {
                return mid;
            }
            else if (origin[mid] < x) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return -1;
    }

BSTreeNode::BSTreeNode() : data(0), lchild(NULL), rchild(NULL) {}

BSTreeNode:: BSTreeNode(int val) : data(val), lchild(NULL), rchild(NULL) {}

BSTreeNode::BSTreeNode(int val, BSTreeNode* left, BSTreeNode* right) : data(val), lchild(left), rchild(right) {}

BSTreeNode::~BSTreeNode(){}

int BSTreeNode::getData() 
{
    return data;
}

BSTreeNode* BSTreeNode::getLChild() {
        return lchild;
    }

BSTreeNode* BSTreeNode::getRChild() {
        return rchild;
    }

void BSTreeNode::setData(int val) {
        data = val;
    }

void BSTreeNode::setLChild(BSTreeNode* left) {
        lchild = left;
    }

void BSTreeNode::setRChild(BSTreeNode* right) {
        rchild = right;
    }

BSTree::BSTree() : num(0), root(NULL) {}

BSTree::BSTree(int n, int* arr) : num(0), root(NULL) {
        for (int i = 0; i < n; i++) {
            addNode(arr[i]);
        }
    }

BSTree::~BSTree() 
{
    clearTree(root);
}

int BSTree::getNum() {
        return num;
    }

BSTreeNode* BSTree::getRoot() {
        return root;
    }

void BSTree::setNum(int n) {
        num = n;
    }

void BSTree::setRoot(BSTreeNode* node) {
        root = node;
    }

void printTemp(BSTreeNode* root, string& result)
{

}

string BSTree::printTree() {
        string result = "";
        preOrder(root, result);
        return result;
    }

bool BSTree::searchNode(int x) {
        return search(root, x);
    }


bool BSTree::addNode(int x) {
        if (root == NULL) { // 空树
            root = new BSTreeNode(x);
            num++;
            return true;
        }
        else if (search(root, x)) { // 元素已在树中
            return false;
        }
        else { // 新增节点
            add(root, x);
            num++;
            return true;
        }
    }

bool BSTree::deleteNode(int val)
{
	BSTreeNode* cur = root, * fro = root;
	while (cur) {
		if (val > cur->getData()) {
			fro = cur; cur = cur->getRChild();
		}
		else if (val < cur->getData()) {
			fro = cur; cur = cur->getLChild();
		}
		else break;
	}
	if (!cur)return 0;
	if (!cur->getLChild() && !cur->getRChild()) {
		if (fro->getLChild() == cur)fro->setLChild(NULL);
		else fro->setRChild(NULL);
		delete cur;
	}
	else if (!cur->getLChild() && cur->getRChild()) {
		fro->setRChild(cur->getRChild());
		delete cur;
	}
	else if (cur->getLChild() && !cur->getRChild()) {
		fro->setLChild(cur->getLChild());
		delete cur;
	}
	else {
		BSTreeNode* Fro = cur->getLChild();
		fro = cur;
		while (Fro->getRChild()) {
			fro = Fro; Fro = Fro->getRChild();
		}
		cur->setData(Fro->getData());
		fro->setRChild(Fro->getLChild());
		delete Fro;
	}
	return 1;
}
void BSTree::clearTree(BSTreeNode* node) { // 释放节点占用的内存
        if (node != NULL) {
            clearTree(node->getLChild());
            clearTree(node->getRChild());
            delete node;
            node = NULL;
        }
    }
void BSTree::preOrder(BSTreeNode* node, string& result) { // 前序遍历二叉排序树
        if (node != NULL) {
            result += to_string(node->getData()) + " ";
            preOrder(node->getLChild(), result);
            preOrder(node->getRChild(), result);
        }
    }
bool BSTree::search(BSTreeNode* node, int x) { // 递归查找二叉排序树中是否包含元素 x
        if (node == NULL) {
            return false;
        }
        else {
            if (node->getData() == x) {
                return true;
            }
            else if (node->getData() < x) {
                return search(node->getRChild(), x);
            }
            else {
                return search(node->getLChild(), x);
            }
        }
    }
void BSTree::add(BSTreeNode* node, int x) { // 递归插入新节点
        if (node->getData() < x) { // 插入右子树
            if (node->getRChild() != nullptr) {
                add(node->getRChild(), x);
            }
            else {
                node->setRChild(new BSTreeNode(x));
            }
        }
        else { // 插入左子树
            if (node->getLChild() != NULL) {
                add(node->getLChild(), x);
            }
            else {
                node->setLChild(new BSTreeNode(x));
            }
        }
    }